# ----------
# User Instructions:
# 
# Create a function compute_value() which returns
# a grid of values. Value is defined as the minimum
# number of moves required to get from a cell to the
# goal. 
#
# If it is impossible to reach the goal from a cell
# you should assign that cell a value of 99.

# ----------

grid = [[0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0]]

init = [0, 0]
goal = [len(grid)-1, len(grid[0])-1]

delta = [[-1, 0 ], # go up
         [ 0, -1], # go left
         [ 1, 0 ], # go down
         [ 0, 1 ]] # go right

delta_name = ['^', '<', 'v', '>']

cost_step = 1 # the cost associated with moving from a cell to an adjacent one.

# ----------------------------------------
# insert code below
# ----------------------------------------

def compute_value():
    value = [[99 for row in range(len(grid[0]))] for col in range(len(grid))]
    open = [goal]
    value[goal[0]][goal[1]] = 0

    while (len(open) > 0):
        c = open.pop()
        y = c[0]
        x = c[1]
        for i in range(len(delta)):
            y2 = y + delta[i][0]
            x2 = x + delta[i][1]
            if (x2 < 0 or x2 >= len(grid[0])): continue
            if (y2 < 0 or y2 >= len(grid)): continue
            if (grid[y2][x2] == 1): continue
            newValue = value[y][x] + cost_step
            if (newValue < value[y2][x2]):
                value[y2][x2] = newValue
                open.append([y2,x2])        

    for i in range(len(value)):
        print value[i]

    return value #make sure your function returns a grid of values as demonstrated in the previous video.

compute_value()
raw_input()